#include <stdlib.h>
#include <stdio.h>
#include <mpi.h>
#include <math.h>
#include <string.h>

void swap(int *p1, int *p2){
	int tmp;
	tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int partition(int* arr, int start, int end){
    int pivot = arr[start];
    int prev = start, cur = start + 1;
    while(cur <= end){
        if(arr[cur] < pivot && ++prev != cur){
            swap(&arr[cur], &arr[prev]);
        }
        cur++;
    }
    swap(&arr[start], &arr[prev]);
    return prev;
}

void quickSort(int* arr, int start, int end){
    if(start < end){
        int idx = partition(arr, start, end);
        quickSort(arr, start, idx - 1);
        quickSort(arr, idx + 1, end);
    }
}

// 以上是串行快速排序的核心部分以及工具函数

int exp2d(int n){
    int expn = 1;
    while(n > 0){
        n--;
        expn <<= 1;
    }
    return expn;
}

int log2d(int n){
    int logn = 1, en = 2;
    while(en < n){
        en <<= 1;
        logn++;
    }
    return logn;
}

void parrallelQuickSort(int* arr, int start, int end, int m, int id, int curId, int N){
    int i, frontLen, idx = end, backLen = -1;
    int *rarr;
    MPI_Status status;
    if(m == 0){
        if(id == curId)
            quickSort(arr, start, end);
        return;
    }// m = 0说明所有的进程已经被分配完毕，可以直接分别执行快速排序了
    if(curId == id){
        while(m > 0 && id + exp2d(m - 1) > N){
            m--;
        }
        if(id + exp2d(m - 1) < N){
            idx = partition(arr, start, end);
            backLen = end - idx;
            // 从当前进程向id + 2^(m - 1)进程传递后半部分的数据
            MPI_Send(&backLen, 1, MPI_INT, id + exp2d(m - 1), curId, MPI_COMM_WORLD);    
            if(backLen > 0){
                MPI_Send(arr + idx + 1, backLen, MPI_INT, id + exp2d(m - 1), curId, MPI_COMM_WORLD);
            }
        }
    }// 这种情况下进程作为发起方将数组序列划分然后将后半部分传递出去
    if(curId == id + exp2d(m - 1)){
        MPI_Recv(&backLen, 1, MPI_INT, id, id, MPI_COMM_WORLD, &status);
        if(backLen > 0){
            rarr = (int*)malloc(backLen * sizeof(int));
            MPI_Recv(rarr, backLen, MPI_INT, id, id, MPI_COMM_WORLD, &status);
        }
    }// 这种情况下进程作为接收方获取数组序列
    frontLen = idx - 1 - start;    
    MPI_Bcast(&frontLen, 1, MPI_INT, id, MPI_COMM_WORLD);
    if(frontLen > 0)
        parrallelQuickSort(arr, start, idx - 1, m - 1, id, curId, N);   // 自身递归地调用快排
    MPI_Bcast(&backLen, 1, MPI_INT, id, MPI_COMM_WORLD);
    if(backLen > 0)
        parrallelQuickSort(rarr, 0, backLen - 1, m - 1, id + exp2d(m - 1), curId, N);    // 让接收方递归地调用快排
    if(curId == id + exp2d(m - 1) && backLen > 0)
        MPI_Send(rarr, backLen, MPI_INT, id, id + exp2d(m - 1), MPI_COMM_WORLD);  // 接收方需要将快排后的数据传回发送方
    if(curId == id && id + exp2d(m - 1) < N && backLen > 0)
        MPI_Recv(arr + idx + 1, backLen, MPI_INT, id + exp2d(m - 1), id + exp2d(m - 1), MPI_COMM_WORLD, &status); // 发送方接收排好序的后半部分数组
}
int main(int argc, char* argv[]){
    int arr[1005];
    int rank, size, n, m;
    // MPI_Status status;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);   // 获取当前进程号
    MPI_Comm_size(MPI_COMM_WORLD, &size);   // 获取总进程数
    if(rank == 0){
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d", &arr[i]);
        }
    }
    m = log2d(size);
    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);   // 由0号进程将n广播到其他进程
    parrallelQuickSort(arr, 0, n - 1, m, 0, rank, size);
    if(rank == 0){
        for(int i = 0; i < n - 1; i++){
            printf("%d ", arr[i]);
        }
        printf("%d", arr[n - 1]);
    }
    MPI_Finalize();
    return 0;
}